#include"BINARYTreeNode.h"
#include"stdlib.h"

BinaryTreeNode* construct(int* preorder,int* inorder,int length){
    if(preorder==NULL||inorder==NULL||length<=0)
        return NULL;
    
    return constructCore(preorder,preorder+length-1,inorder,inorder+length-1);
}

BinaryTreeNode* constructCore(int* startPreorder, int* endPreorder, 
                              int* startInorder,  int* endInorder)
{
    //前序遍历序列的第一个数字是根节点
    int rootValue=startPreorder[0];
    BinaryTreeNode* root=(BinaryTreeNode*)malloc(sizeof(BinaryTreeNode));
    if(root!=NULL){
        printf("内存分配失败");
        exit(EXIT_FAILURE);
    }
    root->value=rootValue;
    root->l=root->r=NULL;
    
    if(startPreorder==endPreorder){
        if(startInorder==endInorder && *startPreorder==*startInorder)
            return root;
        else{
            printf("输入无效");
            exit(EXIT_FAILURE);
        }
    }
    //在中序遍历序列中找到根节点的值
    int* rootInorder=startInorder;
    while(rootInorder!=endInorder&&*rootInorder!=rootValue)
        ++rootInorder;
    if(rootInorder==endInorder&&*rootInorder!=rootValue){
        printf("输入无效");
        exit(EXIT_FAILURE);
    }
    int leftLength=rootInorder-startInorder;
    if(leftLength>0){
        root->l=constructCore(startPreorder+1,startPreorder+leftLength,startInorder,rootInorder-1);
    }
    if(leftLength<startPreorder-endPreorder){
        root->r=constructCore(startPreorder+1+leftLength,endPreorder,rootInorder+1,endInorder);
    }
    return root;
}